#include<map>
#include<string>
#include<stack>
#include<algorithm>
#include<iostream>
using namespace std;

// 代码逻辑的核心错误在于“弹栈条件”和“计数维护”的位置与意义不匹配，导致在某些输入情况下不能正确删除重复字母或保留最小字典序。关键问题点如下：

// mp[st.top()] > 1 这一条件错误使用。
// 弹栈的判断应基于后续字符中是否仍有该字母，而不是 > 1。当前代码在 while 循环中用 mp[st.top()] > 1 来判断是否可以弹出，但 mp 的值只在弹出时减少，未在遍历中动态递减，因此无法正确反映“后续是否还会出现该字母”。应当在每次遍历字符 s[i] 时先执行 mp[s[i]]--，再判断。否则 mp[st.top()] 的值始终比真实剩余次数偏大。

// 未判断栈内是否已存在该字符。
// 按题意，每个字母只能出现一次，若栈中已有 s[i]，应跳过。缺少此判断会导致重复字母入栈，需要额外的 mp1 去后处理，这种方式掩盖了逻辑错误。

// 末尾的“反向+去重”操作只是补救，而非正确算法。
// 正确做法是通过“是否在栈中”的布尔数组控制入栈，而非先压后删。

class Solution {
public:
    string removeDuplicateLetters(string s) {
        map<char, int> mp;
        map<char, bool> inStack; // 记录是否已经加入栈

        for (auto &x:s) mp[x] ++;
        stack<char> st;

        for (int i = 0; i < s.size(); i++) {
            mp[s[i]] --;
            if (inStack[s[i]]) continue;
            while (!st.empty() && s[i] < st.top() && mp[st.top()] > 1) {
                mp[st.top()] -= 1;
                st.pop();
            }
            st.push(s[i]);
        }

        string ans = "";
        while (!st.empty()) {
            ans += st.top();
            st.pop();
        }
        reverse(ans.begin(), ans.end());

        string res = "";
        map<char, bool> mp1;
        for (int i = 0; i < ans.size(); i ++) {
            if (mp1[ans[i]] == false) {
                res += ans[i];
                mp1[ans[i]] = true;
            }
        }

        return res;
    }
};

int main(){
    Solution s;
    string ss = "cbacdcbc";
    cout << s.removeDuplicateLetters(ss) << endl;

    return 0;
}